// 组合 暴力组合
// 输入一个数组，要求返回数组中的n个元素，该方法会返回所有的组合
/**
 *
 * @param {*} arr 输入数组
 * @param {*} max 包含max个元素的所有数组组合
 * @returns
 */
function generateAllCombination(arr, max) {
    arr.sort((a, b) => a - b);
    let count = combinationCount(arr, max);
    console.log(`input: ${JSON.stringify(arr)}, max: ${max}`);
    console.log(`combinationCount: ${count}`);

    let ret = [];

    for (let i = 0; i < arr.length; i++) {
        dfs(arr, max, i, 0, [], ret);
    }

    return ret;
}

function combinationCount(arr, max) {
    let total = arr.length;
    let x = 1;
    let y = 1;

    for (let i = 0; i < max; i++) {
        x = x * (total - i);
        y = y * (i + 1);
    }

    return x / y;
}

function dfs(arr, max, index, level, acc, all) {
    if (acc.length == max || index + level >= arr.length) {
        return;
    }

    acc.push(arr[level + index]);

    for (let i = index; i < arr.length; i++) {
        let newAcc = JSON.parse(JSON.stringify(acc));
        if (level + 1 == max) {
            all.push(acc);
            break;
        }
        dfs(arr, max, i, level + 1, newAcc, all);
    }
}

var ret = generateAllCombination([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 5);

console.table(ret);
